 import java.util.Iterator;
 import java.lang.Object.*;
  public class RandomQueue<Item> implements Iterable<Item>
  {
     private Item[] a = (Item[]) new Object[1];  // queue items
     private int N = 0;                          // number of items
     public boolean isEmpty()  {  return N == 0; }
     public int size()         {  return N;      }
    
     private void resize(int max)
     {  // Move queue to a new array of size max.
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < N; i++)
           temp[i] = a[i];
        a = temp;
	}
	
	public Item get(int i) {
		return a[i];
	}
    
    public void enqueue(Item item) {
    	// Add item to end of queue.
        if (N == a.length) resize(2*a.length);
        a[N++] = item;
    }
    
    public Item dequeue() {
    	if (N == 0) throw new RuntimeException();
    	// Remove item from start of queue.
    	int i = StdRandom.uniform(N);
    	swap(i);
    	Item item = a[--N];
        a[N] = null;  // Avoid loitering.
        if (N > 0 && N == a.length/4) resize(a.length/2);
        return item;
	}
	
	private void swap(int x) {
		Item tmp = a[N-1];
		a[N-1] = a[x];
		a[x] = tmp;
		
	}
	
	public Item sample() {
		if (N == 0) throw new RuntimeException();
		return a[StdRandom.uniform(N)];
	}
    
    public Iterator<Item> iterator() {  QueueIterator qi = new QueueIterator(); qi.copy(); return qi;  }
    
    private class QueueIterator implements Iterator<Item> {
        private int i = N; 
        private Item[] b = (Item[]) new Object[a.length];
        
        public void copy() {
        	for (int j = 0; j < a.length; j++) {
        		b[j] = a[j];
        	}
            	
        }
        
        private void swap(int x) {
        	Item tmp = b[i-1];
			b[i-1] = b[x];
			b[x] = tmp;
        }
        
        public boolean hasNext() {  return i > 0;   }
        
        public Item next()    {
        	int j = StdRandom.uniform(i);
        	this.swap(j);  	
        	return b[--i]; 
        }
        
        public    void remove()  {                  }
	}
	
	public static void main(String args[]) {
    	// Build a queue containing the Integers 1,2,...,6:
    	RandomQueue<Integer> Q= new RandomQueue<Integer>();
    	for (int i = 1; i < 7; ++i) Q.enqueue(i); // autoboxing! cool!
    	// Print 30 die rolls to standard output
    	StdOut.print("Some die rolls: ");
    	for (int i = 1; i < 30; ++i) StdOut.print(Q.sample() +" ");
    	StdOut.println();
		
    	// Let's be more serious: do they really behave like die rolls?
    	int[] rolls= new int [10000];
    	for (int i = 0; i < 10000; ++i)
      		rolls[i] = Q.sample(); // autounboxing! Also cool!
    	StdOut.printf("Mean (should be around 3.5): %5.4f\n", StdStats.mean(rolls));
    	StdOut.printf("Standard deviation (should be around 1.7): %5.4f\n",
		StdStats.stddev(rolls));
    	
    	// Let's look at the iterator. First, we make a queue of colours:
    
   		RandomQueue<String> C= new RandomQueue<String>();
   		C.enqueue("red"); C.enqueue("blue"); C.enqueue("green"); C.enqueue("yellow");
   		//for (int i= 0; i < C.size(); i++) StdOut.println(C.get(i));
   		Iterator I= C.iterator();
   		Iterator J= C.iterator();
   		 
   		StdOut.print("Two colours from first shuffle: ");
   		StdOut.print(I.next()+" ");
   		StdOut.print(I.next()+" ");
   		 
   		StdOut.print("\nEntire second shuffle: ");
   		while (J.hasNext()) StdOut.print(J.next()+" ");

    	StdOut.print("\nRemaining two colours from first shuffle: ");
    	StdOut.print(I.next()+" ");
    	StdOut.println(I.next());
  }
}
